package org.basis.algorithm.greedy;

import java.util.PriorityQueue;

/**
 * 金条切分最小花费问题
 * 这是一个非常典型的哈夫曼编码问题
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金 条，不管切成长度多大的两半，都要花费20个铜板。
 * 一群人想整分整块金条，怎么分最省铜板? 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60。 金条要分成10,20,30三个部分。
 * 如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50;一共花费110铜板。 但是如果先把长度60的金条分成30和30，花费60;
 * 再把长度30金条分成10和20， 花费30;一共花费90铜板。
 * 输入一个数组，返回分割的最小代价。
 *
 * @author Mr_wenpan@163.com 2021/12/27 16:28
 */
public class LessMoneySplitGold {

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40};
        int min = splitCostMin(arr);
        int max = splitCostMax(arr);
        System.out.println("min = " + min + " max = " + max);
    }

    /**
     * 切分金条花费最小问题
     */
    public static int splitCostMin(int[] arr) {
        if (arr == null) {
            return 0;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int item : arr) {
            queue.add(item);
        }
        int sum = 0;
        // 每次取两个最小的求和
        while (!queue.isEmpty() && queue.size() > 1) {
            int cur = queue.poll() + queue.poll();
            sum = sum + cur;
            queue.add(cur);
        }
        return sum;
    }

    /**
     * 切分金条花费最大问题
     */
    public static int splitCostMax(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i : arr) {
            queue.add(i);
        }
        int sum = 0;
        // 每次拿两个最大的数
        while (!queue.isEmpty() && queue.size() > 1) {
            int cur = queue.poll() + queue.poll();
            queue.add(cur);
            sum = sum + cur;
        }
        return sum;
    }
}
